package william.greedy;

import java.util.Arrays;

/**
 * @author ZhangShenao
 * @date 2024/3/31
 * @description <a href="https://leetcode.cn/problems/assign-cookies/description/">...</a>
 */
public class Leetcode455_分发饼干 {
    /**
     * 采用贪心算法实现
     * 首先将g和s两个数组进行排序
     * 然后从g和s的最大值开始,尝试将最大的饼干分给最贪心的小朋友
     * -如果饼干大小可以满足小朋友的要求,则将满足的小朋友数量+1
     * -如果饼干大小无法满足小朋友的要求,则当前小朋友无法被满足,继续处理下一个贪心值更小的小朋友
     * <p>
     * 时间复杂度O(N*logN) 排序O(N*logN) + 遍历数组O(N)
     * 空间复杂度O(1)
     */
    public int findContentChildren(int[] g, int[] s) {
        //边界条件校验
        if (g == null || g.length < 1 || s == null || s.length < 1) {
            return 0;
        }

        //将两个数组排序
        Arrays.sort(g);
        Arrays.sort(s);

        //从最大值开始,遍历两个数组,尝试将当前最大的饼干分给最贪心的小朋友
        int content = 0;
        int gIdx = g.length - 1;
        int sIdx = s.length - 1;
        while (gIdx >= 0 && sIdx >= 0) {
            if (s[sIdx] >= g[gIdx]) {    //饼干可以满足当前小朋友,将计数+1
                content++;
                sIdx--;
                gIdx--;
            } else { //饼干无法满足当前小朋友,继续判断下一个贪心值更小的小朋友
                gIdx--;
            }
        }

        //返回被满足的最大数量
        return content;
    }
}
